package com.leo.algorithm.队列;

import java.util.Collection;

import java.util.HashMap;
import java.util.Iterator;


/***
 * 循环队列
 */
public class LoopQueue<E> implements Queue<E> {

    private int size; //队列大小
    private int front; //队列头指针
    private int tail;//队列尾指针
    private E[] data; //队列数据
    private static final  int DEFAULT_CAPACITY=10; //默认队列容量大小
    public LoopQueue(int capacity){
        data= (E[]) new Object[capacity+1];
        front=0;
        tail=0;
        size=0;
    }
    public LoopQueue(){
        this(DEFAULT_CAPACITY);
    }

    /**
     * 入队
     * @param e
     */
    @Override
    public void enqueue(E e) {
        if(front==(tail+1)%data.length){
            resize(getCapacity()*2);
        }
        data[tail]=e;
        tail=(tail+1)%data.length;
        size++;
    }

    /**
     * 出队
     * @return
     */
    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue is empty");
        }
        E ret = data[front];
        data[front]=null;
        front=(front+1)%data.length;
        size--;
        if(size==getCapacity()/4 && getCapacity()/2!=0){
            resize(getCapacity()/2);
        }
        return ret;
    }

    /**
     * 获取头结点
     * @return
     */
    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue is empty");
        }
        return data[front];
    }

    /**
     * 当前队列大小
     * @return
     */
    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front==tail;
    }

    public int getCapacity(){
        return data.length-1;
    }

    /**
     * 扩容
     * @param newCapacity
     */
    private void resize(int newCapacity){
        E [] newData= (E[]) new Object[newCapacity+1];
        for (int i = 0; i <size ; i++) {
            newData[i]=data[(i+front)%data.length];
        }
        data=newData;
        front=0;
        tail=size;
    }

    @Override
    public String toString() {
        StringBuffer sb=new StringBuffer("front[");
        for (int i = 0; i <size ; i++) {
            sb.append(data[i]+",");
        }
        sb.append("]tail");
        return sb.toString();
    }

    public static void main(String[] args) {
        LoopQueue<Integer> queue = new LoopQueue<>();
        for (int i = 0; i <10 ; i++) {
            queue.enqueue(i+1);
            System.out.println("入队:"+queue.toString());
            if(i%3==2){
                queue.dequeue();
                System.out.println("出队:"+queue.toString());
            }
        }


    }
}
